from CEChain import CEChain
import copy
import sys

class ChainBuilder:
    def __init__(self, funcUnderTest, oracle, verbose=False):
        self.__func = funcUnderTest
        self.__oracle = oracle
        self.__reset()
        self.__verbose = verbose
    
    def __reset(self):
        self.__line = None
        self.__iteration = None
        self.__diff = None
        self.__input = None
        self.__state = None
        
    def __trace_fetch_state(self, frame, event, arg):
        """
        This function traces the function until specified line and iteration, 
        and then records the state of the program in the variable self.__state
        """        
        if event == 'line' and frame.f_lineno == self.__line:
            self.__iteration -= 1
            if self.__iteration == 0:
                self.__state = copy.deepcopy(frame.f_locals)
                return None  # don't get called unnecessarily
        return self.__trace_fetch_state
    
    def __get_state(self, inp, line, iteration):
        '''
         This function allows you to get the state of the program
         at specified line and iteration and return it.
         Complement to the __trace_fetch_state function.
         Gets the state at the_line/the_iteration.        
        '''
        assert line and iteration
        self.__line = line
        self.__iteration = iteration
        sys.settrace(self.__trace_fetch_state)
        self.__func(inp)
        sys.settrace(None)
        return self.__state

    def __trace_apply_diff(self, frame, event, arg):
        '''
         This function traces the function until specified
         line and iteration, and then changes the value of frame.f_locals
         to the supplied values in the_diff.        
        '''
        if event == 'line' and frame.f_lineno == self.__line:
            self.__iteration -= 1
            if self.__iteration == 0:
                frame.f_locals.update(self.__diff)
                return None  # don't get called unnecessarily
        return self.__trace_apply_diff

    def __test(self, diffs):
        line = self.__line
        iteration = self.__iteration
        self.__diff = diffs
        sys.settrace(self.__trace_apply_diff)
        delivered = self.__func(self.__input)
        sys.settrace(None)
        self.__line = line
        self.__iteration = iteration    
        return self.__oracle(self.__input, delivered)
    
    def __ddmin(self, s):
        assert self.__test(s) == "FAIL"    
        n = 2
        while len(s) >= 2:
            start = 0
            subset_length = len(s) // n
            some_complement_is_failing = False    
            while start < len(s):
                complement = s[:start] + s[start + subset_length:]    
                if self.__test(complement) == "FAIL":
                    s = complement
                    n = max(n - 1, 2)
                    some_complement_is_failing = True
                    break
                start += subset_length
            if not some_complement_is_failing:
                if n == len(s):
                    break
                n = min(n * 2, len(s))    
        return s
       
    def __make_locations(self, coverage):
        iterations = {}
        locations = []
        get = iterations.get # make function a local variable
        for line in coverage:
            iterations[line] = get(line,0) + 1
            locations.append((line, iterations[line]))
        return locations
    
    def __auto_cause_chain(self, passing, failing, passingLocations, failingLocations):
        chain = CEChain(self.__func, self.__oracle, passing, failing, passingLocations, failingLocations)
        if self.__verbose:
            print "The program was started with", repr(failing)
        log = {}
        last_reported = None
        for (line, iteration) in failingLocations:
            # get passing and failing states for given location
            self.__state = {}
            state_pass = self.__get_state(passing, line, iteration)  # can be empty if passing execution doesn't cover given location! 
            chain.addValueToChain('PASS', (line, iteration, state_pass))
            
            self.__state = {}
            state_fail = self.__get_state(failing, line, iteration)
            chain.addValueToChain('FAIL', (line, iteration, state_fail))
            # Compute the differences between the passing and failing runs.
            diffs = []
            for var in state_fail.keys():
                if not state_pass.has_key(var) or state_pass[var] != state_fail[var]: # inequality tests are fine for built-in container types
                    diffs.append((var, state_fail[var]))
            chain.addValueToChain('DIFF', (line, iteration, diffs))
     
            # Minimize the failure-inducing set of differences
            self.__input = passing
            self.__line = line
            self.__iteration = iteration
            try:
                cause = self.__ddmin(diffs)
                for var, value in cause:
                    if not log.has_key(var):
                        log[var] = []
                    size = len(log[var])
                    if (size == 0 or log[var][size - 1] != value) and var != last_reported: 
                        chain.addValueToChain('CAUSE', (line, iteration, [(var,value)]))
                        if self.__verbose:
                            print "Then", var, "became", repr(value), '(', line, ',', iteration, ')'
                        last_reported = var
                    log[var].append(value)
            except:
                pass
        chain.finalize()
        if self.__verbose:
            print "Then the program failed."
        return chain

    def getCEChain(self, failingInput, passingInput, failingCoverage, passingCoverage):
        # reset state
        self.__reset()
        # make locations            
        passingLocations = self.__make_locations(passingCoverage)
        failingLocations = self.__make_locations(failingCoverage)
        return self.__auto_cause_chain(passingInput, failingInput, passingLocations, failingLocations)
